/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        714.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 15:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个整数数组prices，其中第i个元素代表了第i天的股票价格 ；非负整数fee 代表了交易股票的手续费用。
//
//你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
//
//返回获得利润的最大值。
//
//注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
#include "../header.h"

class Solution {
public:
    int maxProfit(vector<int> &prices, int fee) {
        /*
        k == infinity 买入次数
        dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
                = max(dp[i - 1][k][1], dp[i-1][k][0] - prices[i])
        dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])

         ==> k都存在，可以消去,加上fee
        dp[i][1] = max(dp[i - 1][1], dp[i-1][0] - prices[i]-fee)
        dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i] )
         */
        int n = prices.size();
        int dp_i_0 = 0, dp_i_1 = INT_MIN, dp_pre_0 = 0;
        for (int i = 0; i < n; ++i) {
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] );
            dp_i_1 = max(dp_i_1, temp - prices[i] - fee);
        }
        return dp_i_0;
    }
};
